/*
  前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
*/

const reConstructBinaryTree = function (pre, vin) {
  // 如果为空树则直接返回
  if (!pre.length || !vin.length) return null
  // 前序遍历的第一个元素为根节点
  const root = new TreeNode(pre.shift())
  // 找到root.val在中序遍历中的索引，则数组被分为两部分，左侧为左子树，右侧为右子树
  const index = vin.indexOf(root.val)
  root.left = reConstructBinaryTree(pre, vin.slice(0, index))
  root.right = reConstructBinaryTree(pre.vin.slice(index + 1))
  return root
}